#leetcode题目24：两两交换链表中的节点
#难度：中等
#时间复杂度：O(n)
#空间复杂度：O(1)
#方法：迭代



class ListNode:
    def __init__(self, data):
        self.val = data
        self.next = None
#TODO 链表类，注意在leetcode中没有这个，纯粹是acm模式下才需要这个
class LinkList:
    def __init__(self):
        self.head = None

    def initList(self, data):
        if not data:
            return None
        
        # 创建头结点
        self.head = ListNode(data[0])
        r = self.head
        p = self.head
        
        # 逐个为 data 内的数据创建结点,建立链表
        for i in data[1:]:
            node = ListNode(i)
            p.next = node
            p = p.next
        return r

    def printlist(self, head):
        if head == None:
            return
        node = head
        while node != None:
            print(node.val, end=' ')
            node = node.next
        print()  # 换行


#核心解法
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        p=head
        new_start=p.next
        while True:
            q=p.next
            temp=q.next
            q.next=p

            if not temp or not temp.next:   
                p.next=temp
                break
            p.next=temp.next
            p=temp

        return new_start

        

#测试数据
list_str=[1,2,3,4]
#预期输出：[2,1,4,3]
head=LinkList().initList(list_str)
solution=Solution()
LinkList().printlist(solution.swapPairs(head))
